package ljl.codetop;

import commons.ListNode;

public class _25_reverse_kgroup {

    /**
     * 思路：先找到 k 个，找到 next，然后翻转链表
     *
     * 我自己写的，过了，写了四十多分钟：
     *   debug 了 30 多分钟
     *   栈溢出了三次
     *   空指针两次
     */
    static class a {

        /**
         * 很好，起码你知道自己测测再提交了
         */
        public static void main(String[] args) {
            System.out.println(new a().reverseKGroup(ListNode.genMockList(), 2));
        }
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || head.next == null || k <= 1) return head;
            ListNode head0 = new ListNode(0, head);
            ListNode prev = head0;
            while (head != null) {
                int i = 0;
                ListNode next;
                ListNode cur = head;
                while (i < k && head != null) {
                    head = head.next;
                    i++;
                }
                if (i == k) {
                    next = head;
                    prev.next = reverse(cur, next);
                    prev = cur;
                } else
                    head = null;

            }
            return head0.next;
        }
        ListNode reverse(ListNode head, ListNode next) {
            if (head == next || head.next == next) return head;
            ListNode tail = reverse(head.next, next);
            head.next.next = head;
            head.next = next;
            return tail;
        }
    }

    static class off1 {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode hair = new ListNode(0, head);
            ListNode pre = hair;

            while (head != null) {
                ListNode tail = pre;
                for (int i = 0; i < k; ++i) {
                    tail = tail.next;
                    if (tail == null) {
                        return hair.next;
                    }
                }
                ListNode next = tail.next;
                myReverse(head, tail);
                pre.next = tail;
                head.next = next;
                pre = head;
                head = next;
            }

            return hair.next;
        }

        // 和我想的不太一样：我的 tail 是 tail.next，他是真的 tail；我是在模仿他，所以我是模仿错了
        public void myReverse(ListNode head, ListNode tail) {
            // prev 初始化为 tail.next 是因为 prev 是下一个元素的 next
            ListNode prev = tail.next;
            ListNode p = head;
            // prev == tail 说明都处理完了
            while (prev != tail) {
                ListNode next = p.next;
                p.next = prev;
                prev = p;
                p = next;
            }
        }
    }

    /**
     * 又写了一遍，又错了无数次
     *
     * 看来还是不太会！
     */
    static class b {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || head.next == null || k == 1) return head;
            ListNode dummy = new ListNode(0, head);
            ListNode prev = dummy;
            while (head != null) {
                int i = 1;
                ListNode start = head;
                while (i < k && head != null) {
                    head = head.next;
                    i++;
                }
                if (i == k && head != null) {
                    ListNode next = head.next;
                    prev.next = reverse(start, head);
                    start.next = next;
                    prev = start;
                    head = next;
                } else
                    break;
            }
            return dummy.next;
        }
        ListNode reverse(ListNode head, ListNode tail) {
            if (head == tail) return head;
            ListNode res = reverse(head.next, tail);
            head.next.next = head;
            head.next = tail;
            return res;
        }

    }

}
